package hot;

public class saner {
    public static int longestValidParentheses(String s) {
        int n=s.length();
        if(n==0||n==1){
            return 0;
        }
        int[] f=new int[n+1];
        s=" "+s;
        int max=0;
        for(int i=1;i<n+1;i++){
            if(s.charAt(i)=='('){
                f[i]=0;
                max=Math.max(f[i],max);
            }else{
                if(s.charAt(i-1)=='('){
                    f[i]=(i-2>=0)?f[i-2]+2:2;
                    max=Math.max(f[i],max);
                }
                if(s.charAt(i-1)==')'){
                    if(s.charAt(i-f[i-1]-1)=='('){
                        f[i]=f[i-1]+2+(i-f[i-1]>=2?f[i-f[i-1]-2]:0);
                        max=Math.max(f[i],max);
                    }
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        String s=")()())";
        int i = longestValidParentheses(s);
        System.out.println(i);
    }
}
